package bintree.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author: yuisama
 * @Date: 2021/9/4 11:27
 * @Description:二叉树的后序遍历
 * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
 */
public class Num145_PostOrder {
    List<Integer> retList = new ArrayList<>();
    // 迭代法
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 上次访问的节点，用来记录右子树是否访问过
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            // 先向左一路走到底
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 此时左树走到底，弹出栈顶元素，但是不能访问，要判断右树是否为空
            cur = stack.pop();
            // 此时右树也为空或访问过右树，可以访问当前节点，同时更新prev指针
            if (cur.right == null || prev == cur.right) {
                retList.add(cur.val);
                prev = cur;
                cur = null;
            }else {
                // 此时右树还未访问，再次将当前节点入栈，同时遍历右树
                stack.push(cur);
                // 访问右树
                cur = cur.right;
            }
        }
        return retList;
    }

//    // 递归法
//    public List<Integer> postorderTraversal(TreeNode root) {
//        if (root == null)
//            return retList;
//        postorderTraversal(root.left);
//        postorderTraversal(root.right);
//        retList.add(root.val);
//        return retList;
//    }
}
